package leetcode.code2234;

import java.util.Arrays;
import java.util.TreeMap;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution4 implements IDebug {
	public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
		int len = flowers.length;
		long diff = 0, num = 0;
		for (int i = 0; i < len; i++) {
			if ((num = flowers[i]) < target) {
				diff += target - num;
			}
		}
		// 花够，随便种，两种挑一个大的，long爆坑
		if (newFlowers >= diff) {
			return Math.max(1l * len * full, 1L * (len - 1) * full + 1l * (target - 1) * partial);
		}
		Arrays.sort(flowers);
		int p = len - 1;
		long grow = newFlowers;
		while ((num = flowers[p]) >= target || grow >= (diff = target - num)) {
			if (num < target) {
				grow -= diff;
			}
			p--;
		}
		TreeMap<Long, Long[]> targets = new TreeMap<>();
		long cur = 0;
		Long sum = 1l * flowers[0], high = 1l * flowers[0];
		for (int i = 1; i < len; i++) {
			cur = flowers[i];
			if (cur != high) {
				long need = cur * i - sum;
				targets.put(need, new Long[] { 1l * i, sum });
			}
			sum += cur;
		}
		targets.put(target * len - sum, new Long[] { 1l * len, sum });
		long ans = 0;
		for (int i = p; i < len; i++) {
//			while (j < len && j * flowers[j] <= grow + sum) {
//				while (j < len && flowers[j] == high) {
//					sum += flowers[j];
//					j++;
//				}
//			}
			Long[] j = targets.ceilingEntry(grow).getValue();
			long max = (j[1] + grow) / j[0];
			cur = 1l * (len - i - 1) * full + 1L * partial * max;
			ans = Math.max(ans, cur);
			if (i != len - 1)
				grow += target - flowers[i + 1];
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(14, this.maximumBeauty(H.str2array3("[1,1,1,3]"), 7, 6, 12, 1));
		H.compare(7411632729l, this.maximumBeauty(H.str2array3(
				"[40742,74654,22547,18738,52156,33325,86828,63276,72224,65874,8268,91224,25184,28,69428,87064,65696,77466,90050,22475,19437,68830,56168,66104,86866,58547,66885,84417,13027,58683,76544,49343,10813,58444,16356,34161,19927,5397,16403,71540,21620,37374,49807,417,39043,38812,28248,71870,42961,40649,94016,19887,84,89541,10629,73203,14892,97132,62660,2370,5380,39769,94599,86931,83186,20501,44885,26943,77669,77891,66153,98865,32787,97342,68662,82740,78887,47815,42860,30637,60297,71183,26976,7776,2269,29377,23165,99864,53895,87432,24455,72667,52752,59991]"),
				3119579236l, 100000, 18353, 74100));
		H.compare(14, this.maximumBeauty(H.str2array3("[1,3,1,1]"), 7, 6, 12, 1));
		H.compare(30, this.maximumBeauty(H.str2array3("[2,4,5,3]"), 10, 5, 2, 6));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
